/**
 * 计数排序
 * @param {*} arr 
 * @returns n+k
 */
function countingSort(arr){
    let len=arr.length,B=[],C=[],min=max=arr[0];
    for(let i=0;i<len;i++){
        min=min<arr[i]?min:arr[i];
        max=max>=arr[i]?max:arr[i];// 找到最大和最小的
        C[arr[i]]=C[arr[i]]?C[arr[i]]+1:1;// 计数+1
    }
    for(let j=min;j<max;j++){
        C[j+1]=(C[j+1]||0)+(C[j]||0)
    }
    for(let k=len-1;k>=0;k--){
        B[C[arr[k]]-1]=arr[k];
        C[arr[k]]--;
    }
    return B;
}
var arr = [2, 2, 3, 8, 7, 1, 2, 2, 2, 7, 3, 9, 8, 2, 1, 4, 2, 4, 6, 9, 2];
console.log(countingSort(arr)); 